The present invention relates to a mask ordering method which controls the way primary keys are compared and relates to a coupling facility (CF) and the accessing of objects within a coupling facility.
A coupling facility (CF) provides a structured means of connecting multiple central processing complexes (CPCs) to allow efficient interchange of data between multiple physical systems while maintaining coherency of the data across all systems. The coupling facility consists of high-speed intersystem (IS) channels, central processing units (CPUs), random-access memory (AND storage that is accessed by the IS channels and CPUs, and control software running in the CPUs.
A coupling facility structure represents a set of objects maintained on behalf of attaching systems. A structure is similar to a shared file in a direct-access storage device (DASD) except that structures are maintained in the coupling facility""s storage. The coupling facility receives commands from attaching CPCs via the IS channels, executes the commands, and returns responses over the IS channels. The commands create, write, read, update, or delete structures on behalf of the attaching CPCs.
In a structure, entries comprise one class of objects that are maintained in storage. Entries may contain name, index, and other values that must be examined and/or updated by the CPU to successfully complete a CF command. The term name in the present specification means the same thing as the term key. The term key is frequently used generically to mean any value for locating an entry in an ordered table. The term name sometimes refers to a key formed of alpha characters, alphanumeric characters or to other limiting characteristics. In coupling facility products and the preset specification, name has no limiting characteristics and is used most generally and interchangeably with key unless the context indicates otherwise.
Coupling facility products from Amdahl Corporation of Sunnyvale, Cailf. and IBM Corporation of Armonk, N.Y., and others have been implemented using S/390-based platforms but coupling facilities can be implemented on any hardware platform. In machines from Amdahl, Amdahl Coupling Control Code (ACCC) is the code that implements the coupling facility functions. In machines from IBM, Coupling Facility Control Code (CFCC) is the code that implements the coupling facility functions.
The S/390 architecture is well-known to represent the foundation for robust, high-performance, high-reliability computing platforms. In IBM-derived publications, such as U.S. Pat. No. 5,537,574 entitled SYSPLEX SHARED DATA COHERENCY METHOD and U.S. Pat. No. 5,317,739 entitled METHOD AND APPARATUS FOR COUPLING DATA PROCESSING SYSTEMS, the coupling facility is referred to as shared cache or shared electronic storage (SES).
A cache structure represents an intermediate level of a three-tiered data hierarchy where the highest level is the local cache copies of data objects within a CPC and the lowest level is copies of data on shared DASD. Application programs that participate in such a data hierarchy can write and read cache entries in a CF cache structure. Each cache entry is identified by a name. The entries are organized in a logical construct referred to as the directory. A command issued to the CF may request processing of one specific entry or a group of related entries.
In cache structures, several cache commands process cache entries having a name that matches the input name under an input name mask. One such a command is the invalidate-name command. (The invalidate-name command is referred to as the IXLCACHE REQUEST=DELETE_NAME request in the OS/390 MVS Programming: Sysplex Services Guide (GC28-1771) from IBM [hereafter Sysplex Services Guide]). In the Sysplex Services Guide, the input name mask is 16 bits and the input name is 16 bytes. The 16 bits correspond one for one with the 16 bytes of the name. The name comparison is successful when all the name bytes having a corresponding name mask bit of one, are equal. A mask of all zeros causes all names to be processed. A mask of all ones identifies a single name to be processed. Processing, in the case of the invalidate-name command, for example, can range from updating the cache entry to deleting the entry, depending on the values of the other input parameters.
An example that illustrates the naming and masking concepts is given where, for purposes of the example, keys are 4-character names consisting of only the alphabet letters A and B. Assume a cache structure has the following set of name entries:
AABA, ABAA, ABAB, BAAA, BABA, BBAB.
For the above set of name entries, an invalidate-name command specifying an input name AAAA and an input mask of bxe2x80x980100xe2x80x99 invalidates the following entries:
AABA, BAAA and BABA.
For good performance, the utilization of the cache structure requires that an entry corresponding to a specified name be quickly located. Different methods for quickly locating names have been used and proposed. For IBM systems, directories in the form of hash tables have been employed and for Amdahl systems, directories in the form of binary trees have been employed.
For operations of coupling facilities in systems prior to IBM CFLEVEL=7, when the name mask is not all ones, all entries in the cache structure directory have to be scanned to find all the names matching the specified name mask. In cases where the set of entries which match the specified name mask is small compared to the total number of entries in the structure, this scanning process is inefficient and time-consuming.
Some applications on CPCs use invalidate-name with a name mask to perform selective deletion of entries from the cache when, for example, a particular data set is closed, shut down, or ceases to have a shared interest that requires its data to reside in the cache. In these cases, a known naming convention defines the name mask which is used to select the entries to be deleted. In such cases, the full directory scan performed by the invalidate-namne operation adversely impacts the performance of the applications which are using it to perform cleanup.
For operations using IBM CF-Level 7 Improvements (CFLEVEL=7 and higher), a cache structure supports xe2x80x98name classesxe2x80x99 for names adhering to a naming convention defined when the structure is created (via the name class mask). Specifically, names that are identical in byte positions corresponding to bits which are on in the name class mask belong to the same name class. In the IBM implementation, name class queues are used to group together all entries that are processed as a group given the defined naming convention. Later, when an invalidate-name command is requested using a name mask equal to the name class mask for the structure, all of the entries to be deleted can be located efficiently by running through the name class queue, avoiding the overhead of scanning through all of the entries in the structure. The efficiency of application processes that invoke invalidate-name for cleanup purposes is therefore improved. Examples of name classes can be found in the section xe2x80x9cUsing Name Classes in a Coupling Facilityxe2x80x9d in the Sysplex Services Guide.
Again, consider the following set of name entries:
AABA, ABAA, ABAB, BAAA, BABA, BBAB.
For that set of name entries and with a name class mask of xe2x80x980110xe2x80x99 specified at structure creation time, the following name classes and members are created where underscores indicate name bytes that identify the name class:
Name class AA: BAAA
Name class AB: AABA, BABA
Name class BA: ABAA, ABAB, BBAB
Name class BB: (empty)
In the IBM CFLEVEL=7 implementation, two programming constructs are used for performance enhancement, one for quickly locating a single cache entry by name and another one for locating entries in a specified name class. For locating a single entry by name, a hash table construct is used as described in the section xe2x80x9cHash Accessing of SES Directory Entriesxe2x80x9d in U.S. Pat. No. 5,537,574. For locating entries in a name class, name class queues are used; however, enhanced efficiency is provided only when the specified name mask is identical to the name class mask (specified when the structure is allocated). When the specified name mask is not identical to the name class mask, the IBM CFCC resorts to scanning the entire cache directory.
While a separate construct, such as name class queues can be employed, there is a need for improvements which support name classes without the additional processing and storage overhead of maintaining separate name class queues and without adverse impact on established methods for quickly finding names.
The present invention is a mask ordering method and apparatus which controls the way keys are compared. In its general form, the mask ordering method operates to order (with a less than, greater than or equal to comparison) two N-byte (for example, N=16) keys (Name_1 and Name_2) using an N-bit ordering mask where the N bits in the ordering mask correspond one for one with the N bytes in the keys in the same compare direction (either left-to-right or right-to-left). The mask ordering method operates as follows:
A comparison of the two N-byte keys, Name_1 and Name_2, proceeds in a compare direction byte by byte, first for those bytes where the corresponding mask bit is on, and then for those bytes where the corresponding mask bit is off. This byte-position order in which the bytes are compared is hereafter referred to as the compare order.
The byte-by-byte processing continues in the compare order by comparing each corresponding byte in Key_1 and Key_2 until the order of Key_1 relative to Key_2 is determined.
When applying the mask ordering method to organize name classes in a coupling facility (CF) cache structure, each 16-byte cache entry name is an N-bit key (with N=16); the 16-bit name class mask fixed at the creation of the cache structure is an N-bit ordering mask (with N=16). The CF command architecture dictates that the compare direction be left-to-right.
By ordering all cache name entries using the mask ordering method, those entries belonging to the same name class fall into contiguous positions. Furthermore, within a name class, entries are ordered by those name bytes corresponding to name-class-mask bits that are zeros. Name classes are ordered by those name bytes corresponding to name-class-mask bits that are ones.
An embodiment of the invention is particularly useful in a coupling facility (CF) cache structure where operations on names and name classes in a directory, such as the invalidate name command, are performed.
The present invention uses the same programming construct to locate a single cache entry and a specified name class of entries efficiently and without resorting to scanning the entire cache directory.
The present invention does not reduce the speed of searching, inserting and deleting single cache entries while still being able to operate on both single entries and classes of entries.
The present invention minimizes the need for storage overhead as is required for name class queues while being easily integrated into existing systems.
The present invention allows the identification of groups of entries which are particular subsets or supersets of a name class, and provides an efficient method for their retrieval.
The foregoing and other objects, features and advantages of the invention will be apparent from the following detailed description in conjunction with the drawings.